import java.util.ArrayList;
import java.util.List;

class Solution {
    //剑指 Offer 05. 替换空格
    public String replaceSpace(String s) {
        StringBuffer str=new StringBuffer();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)==' '){
                str.append("%20");
            }else{
                str.append(s.charAt(i));
            }
        }
        return new String(str);
    }
    //剑指 Offer 04. 二维数组中的查找
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int i = matrix.length - 1, j = 0;
        while(i >= 0 && j < matrix[0].length)
        {
            if(matrix[i][j] > target) {
                i--;
            }else if(matrix[i][j] < target) {
                j++;
            }else{
                return true;
            }
        }
        return false;
    }
    public String reverseLeftWords(String s, int n) {
        if (s == null || s.length() == 0) {
            return s;
        }
        n %= s.length();
        char[] ch = s.toCharArray();
        reverse(ch, 0, n-1);
        reverse(ch, n, s.length() - 1);
        reverse(ch, 0 ,s.length() - 1);
        System.out.println(new String(ch));
        return  new String(ch);
    }

    /**
     * 逆序调整start到end之间的元素顺序
     */
    public void reverse(char[] ch, int start, int end) {
        while (start < end) {
            char tmp = ch[start];
            ch[start] = ch[end];
            ch[end] = tmp;
            start++;
            end--;
        }
    }
    //剑指 Offer 58 - I. 翻转单词顺序
    public String reverseWords(String s) {
        s=s.trim();
        String[] strs = s.split(" ");
        StringBuilder res = new StringBuilder();
        for(int i = strs.length - 1; i >= 0; i--) {
            if(strs[i].equals("")) continue;
            res.append(strs[i] + " ");
        }
        return res.toString().trim();
    }
    //剑指 Offer 57 - II. 和为s的连续正数序列
    public int[][] findContinuousSequence(int target) {
    int left = 1; 
    int right = 1;
    int sum = 0; 
    List<int[]> res = new ArrayList<>();
    while (left <=target/2+1) {
        if (sum < target) {
            sum += right;
            right++;
        } else if (sum > target) {
            sum -= left;
            left++;
        } else {
            int[] arr = new int[right-left];
            for (int k = left; k < right; k++) {
                arr[k-left] = k;
            }
            res.add(arr);
            sum -= left;
            left++;
        }
    }
    return res.toArray(new int[res.size()][]);
}
}